MENTAL, una Gramática Sintáctico-Semántica

MENTAL, UNA
GRAMÁTICA
SINTÁCTICO-
SEMÁNTICA

“El hombre que habla con imágenes primordiales habla con mil lenguas” (Jung)

“El estudio de la gramática, en mi opinión, es capaz de arrojar mucha más luz sobre cuestiones filosóficas que las comunmente supuestas por los filósofos” (Bertrand Russell)

Gramática Sintáctica
Una gramática sintáctica o formal −también llamada “gramática generativa”− es un metalenguaje que especifica o describe la sintaxis (la forma) de las diferentes sentencias de un lenguaje. En el caso de un lenguaje de programación, la gramática describe la estructura de los elementos pasivos (datos) y a los activos (procesos), lo que constituye una unificación metalingüística de estos dos tipos de elementos en el aspecto sintáctico.

Una gramática formal consta de 4 elementos:

Un conjunto T de elementos terminales.
Un conjunto N de elementos no terminales.
Un conjunto P de producciones (o reglas de producción) del tipo α ::= β. La parte izquierda α es un elemento no terminal. El símbolo “::=” significa “se define como”. La parte derecha β es una secuencia de elementos terminales y no terminales. La longitud de la secuencia es el número de elementos de que consta. Existe la secuencia vacía, que tiene longitud cero.
Un elemento no terminal S designado como elemento no terminal inicial.

El lenguaje asociado a una gramática es el conjunto de secuencias finitas generado por dicha gramática a partir del elemento no terminal inicial. De ahí el nombre de “gramática generativa”.

Dos gramáticas son equivalentes si generan o describen el mismo lenguaje. El lenguaje generado por una gramática puede ser finito o infinito.

La notación BNF

Inventada por John Backus [1959], inicialmente se llamó “Backus Normal Form” (Forma Normal de Backus). Esta notación se adoptó para describir el lenguaje de programación Algol 60. La aportación de Peter Naur [1963] en la edición del informe sobre Algol 60 hizo que la notación BNF se conociera como "Backus Naur Form" [Knuth, 1964].

En la notación original BNF sólo se contemplaban dos mecanismos de estructuración de la información:

Composición.
Corresponde a la secuencia de elementos (terminales o no). No se utiliza ningún símbolo específico.
Alternativa.
Representa una elección entre diferentes secuencias. Se expresa mediante el símbolo “|”.

Esta notación era claramente insuficiente y apareció la EBNF (Extended BNF, BNF extendida), de la que existen muchas variantes. El objetivo era reducir el número de reglas de producción y aumentar la legibilidad. La más difundida contempla adicionalmente los mecanismos:

Agrupación de alternativas.
Se expresa mediante paréntesis.
Repetición
De un elemento cero o más veces (*) o una o más veces (⁺).
Opcional
Indica que puede o no aparecer. Se expresa mediante corchetes: [ ].

Ejemplos:

⁺

Limitaciones de la notación EBNF

La gramática generativa es realmente una teoría de la sintaxis, pues no se considera la semántica. Es por ello que, a pesar de haber impulsado el estudio de las gramáticas y la formalización de la sintaxis, se le ha criticado por no ofrecer un modelo semántico para los lenguajes.
El mecanismo de repetición está muy limitado, pues no es posible indicar un número de concreto de repeticiones.
Se hace referencia únicamente a propiedades libres de contexto. Por lo tanto, no se pueden especificar restricciones estructurales ni funcionales, por ejemplo, condiciones, atributos, etc.

La naturaleza genérica de la notación EBNF

La notación EBNF es realmente un meta-metalenguaje, es decir, es un lenguaje para definir metalenguajes de lenguajes concretos.

EBNF, como lenguaje en sí, es un lenguaje de alto nivel, en el que varios autores han creído ver un poderoso formalismo, de naturaleza genérica, que puede, por si mismo, usarse como lenguaje de programación, como lenguaje de especificación formal, como fundamento de una ciencia o teoría de los lenguajes de programación y de la propia programación [Harrison, 1965] [Gries, 1981] [Schmidt, 1982].

Gramática Semántica
Así como en las gramáticas sintácticas tradicionales se manejan categorías abstractas (que tienen normalmente relación con la propia estructura del lenguaje), las gramáticas semánticas están estructuradas y organizadas en base a categorías lexicales, es decir, en conceptos, categorías o propiedades semánticas concretas relativas a un dominio, como por ejemplo, tiempo, lugar, color, objetos, etc.

Las características principales de las gramáticas semánticas son:

Las sentencias de una gramática semántica especifican las relaciones permitidas entre los conceptos de un dominio de aplicación, más allá de su descripción meramente formal (cubierta por una gramática sintáctica tradicional).
Normalmente se utilizan reglas para relacionar los conceptos. Son “reglas semánticas”, en lugar de “reglas sintácticas” (en forma de producciones), aunque hay una cierta semejanza entre ellas.
Mientras que en una gramática sintáctica se realiza un análisis orientado exclusivamente a verificar la sintaxis correcta de una sentencia, en una gramática semántica se realiza adicionalmente un análisis semántico, que proporciona la estructura que relaciona los conceptos o categorías encontradas. Esta estructura, en su caso más general, es una “red semántica”, es decir, una red de conceptos interrelacionados.
Para el interprete que realiza el análisis, lo más importante es el análisis semántico, pues siempre intenta “comprender” el significado, que es lo importante, por lo que se permite una cierta flexibilidad sintáctica.
Las gramáticas semánticas son relativamente fáciles de desarrollar para dominios limitados, cuando hay pocos conceptos en juego. Pero son difíciles de extender para que cubran nuevos dominios. Para solventar esto, se utilizan las “gramáticas semánticas modulares” en las que:
- Hay una gramática semántica en cada dominio, organizada en forma de reglas.
- Hay un conjunto de reglas compartidas por todos los dominios para relacionar conceptos comunes.
Las gramáticas semánticas tienen su aplicación principal en el análisis del lenguaje natural, con el objeto de descubrir, identificar y relacionar los conceptos subyacentes que se ocultan en las sentencias para ayudar a su posterior comprensión o interpretación. De hecho, fueron desarrolladas con el objetivo de añadir semántica a las gramáticas tradicionales en el análisis de subdominios del lenguaje natural [Burton, 1976].

De todas formas, la frontera entre los dos tipos de gramáticas (sintácticas y semánticas) es un tanto difusa. Por ejemplo, las gramáticas formales de los lenguajes de programación se pueden considerar también semánticas, pues además de un análisis sintáctico, se genera una estructura que relaciona las entidades o categorías contempladas por el lenguaje.

MENTAL como Gramática Sintáctico-Semántica
MENTAL permite expresar la notación EBNF, por lo que tiene, al menos, su mismo poder expresivo. Por lo tanto, sirve para definir gramáticas sintácticas.

Mecanismo	EBNF	MENTAL
Definición	::=	`=:` (sustitución potencial)
Composición de x, y, z, …	xyz...	`(x y z …)`
Alternativa entre x, y, z, …	x\|y\|z\|...	`∈{x y z …}` (pertenencia a un conjunto)
Repetición de x 0 o más veces	x*	`x★[0…]`
Repetición de x 1 o más veces	x⁺	`x★[1…]`
Secuencia vacía	no existe símbolo	`θ` (expresión nula)
x opcional	[x]	`∈{x θ}`

MENTAL es una gramática semántica universal, pues permite relacionar, sin restriccines, conceptos presentes en todos los dominios.

Desde el punto de vista de MENTAL, una gramática formal G es una expresión extensiva o intensiva que describe todas las sentencias de un lenguaje. Lenguaje y gramática se confunden. En el caso de un lenguaje infinito, la expresión que describe el lenguaje es recursiva.

Ejemplos

Tenemos un robot que se mueve en una sola dirección: hacia adelante (a) o hacia atrás (b). Un viaje V del robot es una secuencia de movimientos que finalizan en el punto de partida. En medio del viaje puede iniciarse otro viaje.

El lenguaje se define mediante la siguiente expresión recursiva:
Una forma más simple es:
en donde θ es el viaje nulo, es decir, sin desplazamiento.

Ejemplos de viajes: aabb, baba, abab, ababaabb, etc.

Todo viaje tiene una longitud (la longitud de la secuencia). El viaje mínimo tiene longitud 2.
Un viaje en las cuatro direcciones.
Es una generalización del ejemplo anterior. Las 4 direcciones son: arriba (a), abajo (b), izquierda (i) y derecha (d).

El lenguaje se define mediante la siguiente expresión recursiva:
Ejemplos de viajes: aidb, aaabbb, aiiidddb, iiaabbdd, etc.

También podríamos haber utilizado otra notación que reflejara los caminos opuestos:
Números binarios.
El lenguaje se expresa también de forma recursiva:
Ejemplos de números binarios: 0, 1, 01, 10, 11, 011, 111000, etc.

Todo número binario tiene una longitud (la longitud de la secuencia de dígitos). El número binario mínimo tiene longitud 1.

En los tres ejemplos los lenguajes son infinitos.

Lenguaje parametrizado

La definición de un lenguaje puede parametrizarse. En el ejemplo de los números binarios, podemos considerar, por ejemplo:

Los números de longitud n:

⟨( B(n) =: ([[0 1]★n] ) )⟩
Los números de longitud menor o igual que n:

⟨( B(n) =: ([[0 1]★[1…n]] ) )⟩

Ventajas de MENTAL como gramática

Se diluye la distinción entre gramática y lenguaje. No son necesarios los conceptos asociados a la definición de gramáticas: “regla de producción”, “elemento terminal” y “elemento no terminal”, ni tampoco se necesita el “elemento no terminal inicial”.
Se integra lo que es la semántica formal con la semántica de utilización (pragmática), diluyéndose la distinción entre la especificación de lenguajes particulares y aplicaciones.
Se diluye la distinción entre gramática semántica y ontología. Una ontología es un conjunto de clases o conceptos y relaciones entre ellos para modelar, fundamentar, describir y representar un dominio.
No se necesita ningún lenguaje específico como EBNF o las expresiones regulares. Se dispone de un lenguaje universal, completo, formal, con todo su poder expresivo y flexibilidad de especificación. Por ejemplo, se puede especificar el número de repeticiones concretas, se pueden definir rangos de valores, utilizar distribuciones, expresiones paramétrizadas, condiciones, atributos, etc.
Hay una relación biunívoca entre sintaxis y semántica. Y no es necesario distinguir entre gramática sintáctica y gramática semántica. Son dos aspectos de una misma cosa.

La orientación es sintáctico-semántica. Se ofrecen mecanismos para definir “cómo son”, para desarrollar los elementos del lenguaje, tanto a nivel semántico como sintáctico. En una gramática sintáctica se ofrecen mecanismos para definir “cómo pueden ser” los elementos, pero sólo a nivel sintáctico.
El constructo básico de una gramática sintáctica es la regla de producción del metalenguaje utilizado. Con MENTAL podemos utilizar la potencia de las primitivas del lenguaje.
Se pueden especificar gramáticas de orden superior (y sus correspondientes lenguajes), gramáticas y lenguajes interrelacionados, etc.
La sintaxis es flexible, pues puede modificarse dinámicamente, incluso la inicialmente definida por las primitivas a través del mecanismo de las operaciones derivadas.
Cada construcción sintáctica o expresión compuesta tiene asociada una semántica perfectamente definida. Es la llamada “Semántica Composicional”: el significado de una expresión compuesta se deriva de los significados de las expresiones componentes.
Hay libertad constructiva. Una gramática impone ciertas restricciones combinatorias. En MENTAL, la gramática semántica es libre, se permiten todas las combinaciones posibles, sin restricciones. MENTAL puede imponer restricciones en la definición de lenguajes, pero en sí mismo carece de limitaciones. Y así tiene que ser, puesto que en MENTAL están todas las posibilidades de las primitivas semánticas universales.
MENTAL puede especificar cualquier forma de gramática sintáctico-semántica, más allá de las gramáticas tradicionales.
El lenguaje está abierto (a nuevas construcciones sintáctico-semánticas). Esto justifica que no se defina para MENTAL una gramática clásica (sintáctica) porque definirla implicaría limitarlo. En una gramática sintáctica, el lenguaje está cerrado sintácticamente.
Todos los lenguajes están unidos por una semántica común, pues siempre se utiliza la misma gramática sintáctico-semántica. En una gramática sintáctica todos los lenguajes están desconectados y separados, pues cada uno utiliza una gramática sintáctica diferente.
El compilador o intérprete es universal. Es válido para todos los lenguajes. En una gramática sintáctica, hay que desarrollar un intérprete o compilador específico para cada lenguaje. En una gramática sintáctica hay un proceso de análisis sintáctico (parsing).
Se normaliza la sintaxis y la semántica de todos los lenguajes, al basarse en las mismas primitivas semánticas. Con una gramática sintáctica se normaliza la sintaxis de todos los lenguajes, siempre que se utilice el mismo metalenguaje sintáctico.

MENTAL como lenguaje y metalenguaje

MENTAL es un lenguaje y un metalenguaje:

Es un lenguaje para desarrollar aplicaciones mediante las primitivas semánticas universales.
Es un metalenguaje, pues permite describir lenguajes específicos mediante gramáticas.
Es un meta-metalenguaje, pues es un metalenguaje que permite especificar los metalenguajes que describen lenguajes concretos.
Es un meta-meta-metalenguaje, etc. Hay infinitos niveles.
Es un lenguaje universal, pero también es un metalenguaje universal, pues permite definir lenguajes (e incluso otros metalenguajes) particulares. MENTAL no es un metalenguaje de sí mismo, pero puede expresar el metalenguaje de otros lenguajes. MENTAL es el fundamento de todos los lenguajes.

Adenda
Orígen de las gramáticas formales

El concepto de gramática proviene del campo de la lingüística. El concepto de gramática formal tiene su origen en la lingüística moderna, cuyo máximo representante es Noam Chomsky [1956], que desarrolló un lenguaje simbólico de tipo descriptivo que permitía explicar el ilimitado poder expresivo de los lenguajes naturales al basarse en mecanismos recursivos.

En informática, la idea de gramática formal adquirió una gran importancia para la definición de lenguajes de programación y de todo tipo de lenguajes en general.

Clasificación de las gramáticas y los lenguajes

Las gramáticas se clasifican en:

Tipo 0 o no restringidas.
No hay restricciones en las reglas α ::= β, excepto que α no puede ser la cadena o secuencia vacía.
Tipo 1 o sensibles al contexto.
Las reglas son de la forma α₁1Aα₂. Es decir, A se puede reemplazar por β si se encuentra entre α₁ y α₂ (que son el contexto).

A es un elemento no terminal.
α₁, α₂ y β son secuencias de elementos (terminales o no).
α₁ y α₂ pueden ser cadenas vacías.
Tipo 2 o libres de contexto (gramáticas de Chomsky).
Es un caso particular del tipo 1 cuando α₁ y α₂ son cadenas vacías.
Las reglas son, por lo tanto, de la forma A ::= β
Tipo 3 o regulares (gramáticas de Kleene).
Es un caso particular del tipo 2.
Las reglas son de la forma A ::= aB ó A ::= a.
A y B son elementos no terminales y a es un elemento terminal.

La jerarquía de gramáticas se manifiesta en lo siguiente:

Toda gramática regular es libre de contexto. Toda gramática libre de contexto es sensible al contexto. Toda gramática sensible al contexto es no restringida. Los lenguajes de tipo n son los lenguajes generados por una gramática de tipo n.

Bibliografía

Aho, Alfred V.; Sethi, Ravi y Ullman, Jeffrey D. Compiladores. Principios, Técnicas y herramientas. Addison-Wesley Iberoamericana, 1990.
Backus, John. The syntax and semantics of the proposed international algebraic language of the Zurich ACM-GAMM Conference. International Conference on Information Processing, Junio 1959, UNESCO, París. pp. 125-132.
Burton, Richard R. Semantic Grammar: An Engineering Technique for Constructing Natural Language Understanding Systems. Report 3453, Bolt, Beranek and Newman Inc., December 1976.
Chomsky, Noam. Three models for the description of language. IEEE Trans. on Information Theory, vol. 2, no. 3, pp. 113-124, 1956.
Gries, David. The Science of Computer Programming. Springer-Verlag, 1981.
Harrison, M.A. Introduction to switching and automata theory. McGraw-Hill, New York, 1965.
Harrison, M.A. Introduction to formal languages theory. Addison-Wesley, Reading, Mass., 1978.
Knuth, Donald Ervin. Backus Normal Form vs. Backus Naur Form. Communications of the ACM, vol. 7, no. 7, Dec. 1964, pp. 735-736.
Meyer, Bertrand. Introduction to the Theory of Programming Languages. Prentice Hall International Series in Computer Science, C.A.R. Hoare Series Editor, 1990.
Naur, Peter. Revised Report on the Algorithmic Language Algol 60. Comm. ACM. vol. 6, no. 1, pp. 1-17, 1963.
Schmidt, David A. Denotacional semantics as a programming languaje. University of Edimburgh, Dept. of Computer Science, Reino Unido, 1982.